#include<iostream>
#include<windows.h>
using namespace std;
string s="0000000000000000000000000000"; //28 char

void print_one(string s,int k) {
	cout << "   __________________" << endl;
	for (int i = 0; i < 3; i++) {
		cout << "  /" ; 
		for (int j = 0; j < 3; j++) {
			if (s[k]=='1') printf("%3c  /",'X');
			else if (s[k]=='2') printf("%3c  /",'O');
			else printf("%3d  /",k);
			k++;
		}
		cout << endl<< " /_____/_____/_____/" ;
		if (k%9==1) cout <<  endl;
		else cout << "_"<< endl;
	}
} 
void print(string s) {
	print_one(s,1); // 1...9
	print_one(s,10);// 10...18
	print_one(s,19);// 19...27
}


char win(string s) {
	int wins[48][3] ={{1,2,3}, {4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},
	{3,5,7},{1,5,9},{10,11,12},{13,14,15},{16,17,18},{10,13,16},
	{11,14,17},{12,15,18},{10,14,18},{12,14,16},{19,20,21},{22,23,24},
	{25,26,27},{19,22,25},{20,23,26},{21,24,27},{19,23,27},{21,23,25},
	
	 
  	{1,11,21},{4,14,24},{7,17,27},{1,13,25},{2,14,26},{3,15,27},
	{1,14,27},{7,14,21}, {3,11,19},{6,14,22}, {9,17,25}, {7,13,19},
	{8,14,20}, {9,14,19},{1,10,19},{2,11,20},{3,12,21},{9,15,21},
	{4,13,22},{5,14,23},{6,15,24},{7,16,25},{8,17,26},{9,18,27}}; 
		for (int i = 0; i < 48; i++) {
		if (s[wins[i][0]] != '0' &&
			s[wins[i][0]] == s[wins[i][1]] && s[wins[i][1]] == s[wins[i][2]])
			{
				return s[wins[i][2]];
			}
	}
	return '0';
}
char cp(char player) { //change player 1->2,2-1 
	if (player=='1') 
		return '2';
	return '1';
} 

int minimax(string s, int depth, char player) {
	int score = -1000;
	if (depth > 3) {
		return 0;
	}
	int move = -1;
	for(int i=1;i<=27;i++) {
		if (s[i] == '0') {
			if (player==1) s[i] = '1';
			else s[i] = '2';
			int thisScore = -minimax(s, depth+1, cp(player));
			if (thisScore > score) {
				score = thisScore;
				move = i;
			}
			s[i] = '0';//reset like dfs
		}
	}
	if (move == -1)  // is full
		return  0;
	return score;
}

int computer(string s) {
	int player = 2;
	int move = -1,score = -1000,tmpScore;
	for (int i = 1; i<= 27; i++) {
		if (s[i] == '0') {
			s[i] = '2';
			char winner = win(s);
			if (winner != '0') {
				move = i;
				score = 101;
				s[i] = '0';
				break; 
			} else {
				tmpScore = -minimax(s, 0, cp(player));
				if (tmpScore > score) {
					score = tmpScore;
					move = i;
				}
			}
			s[i] = '0';//reset like dfs
		}	
		
	}
	if (score==101) 
		return move;
	player = cp(player); // change
	for(int i=1;i<=27;i++) {
		if (s[i] == '0') {
			s[i] = '1';
			char winner = win(s);
			if (winner != '0') {
				move = i;
				score = 100;
				s[i] = '0';
				break; 
			} else {
				tmpScore = -minimax(s, 0, cp(player));
				if (tmpScore > score) {
					score = tmpScore;
					move = i;
				}	
			}
			s[i] = '0';//reset like dfs
		}
	}
	
	return move;   
}
bool check(string s) {//check if win
	if (win(s) != '0') {
		return true;
	}
	return false;
}
	
int main() {
	int player, start;
	while(true) {
		cout << "Choose player1 or player2 (1/2): "  ;
        cin >> start; 
        if (start == 1) {
        	player = 1;
			break;
        } else if (start == 2) {
        	s[5]='2';
        	player = 1;
        	break;
		} else {
			cout << "Try again " << endl;
		}
    }
	
	while(!check(s)) {
		system("cls");
		print(s);
		if (player==1) {
			int n;
			cout << "choose the number: "  ;
			cin >> n;
			if (n>=1 && n<=27 && s[n]=='0') {
				s[n] = '1';
				player = 2;
			} else {
				cout << "wrong number ! " << endl;
				continue;
			}
		} else {
			cout << "Computer thinking ......" << endl;
			int ans = computer(s);
			s[ans] = '2'; 
			player = 1;
		}
	}
	system("cls");
	print(s);
	char winner = win(s);	//check if win
	if (winner != '0') {
		if (winner == '1') cout << "player1 win!!!" << endl;
		else cout << "player2 win!!!" << endl;
		return true;
	}	
	return 0;
}

